package com.suo.AVL;

import java.nio.BufferUnderflowException;

public class AVL {
    private static class AvlNode {
        AvlNode(Integer theElement) {
            this(theElement,null,null);
        }

        public AvlNode(Integer element, AVL.AvlNode left, AVL.AvlNode right) {
            this.element = element;
            this.left = left;
            this.right = right;
            height = 0;
        }

        //节点中的数据
        Integer element;
        //左孩子
        AVL.AvlNode left;
        //右孩子
        AVL.AvlNode right;
        //树高
        int height;
    }

    //根节点
    private AvlNode root;

    //允许的平衡因子
    private static final int ALLOWED_IMBALANCE = 1;

    //无参构造
    public AVL() {
        root = null;
    }

    //清空树
    public void makeEmpty() {
        root = null;
    }

    //判断树是否为空
    public boolean isEmpty() {
        return root == null;
    }

    //判断树是否含有某个节点
    public boolean contains(Integer x) {
        return contains(x,root);
    }

    //寻找这颗树的最小值
    public Integer findMin() {
        if (isEmpty()) throw  new BufferUnderflowException();
        return findMin(root).element;
    }

    //寻找这颗树的最大值
    public Integer findMax() {
        if (isEmpty()) throw  new BufferUnderflowException();
        return findMax(root).element;
    }

    //插入操作
    public void insert(Integer x) {
        root = insert(x,root);
    }

    //删除操作
    public void remove(Integer x) {
        root = remove(x,root);
    }

    //遍历操作
    public void printTree() {
        printTree(root);
        System.out.println();
    }

    /**
     * 获取树高
     * @param t
     * @return
     */
    private int height(AvlNode t) {
        return  t == null ? -1 : t.height;
    }

    /**
     * 如果相等则返回本节点，如歌比根节点小则递归左子树，如果比根节点大则递归右子树
     * @param x
     * @param t
     * @return
     */
    private boolean contains(Integer x, AvlNode t) {
        if(t == null) return false;
        if(x == t.element) return true;
        else if(x < t.element) return contains(x,root.left);
        else return contains(x,root.right);
    }

    /**
     * 一直往左走
     * @param t
     * @return
     */
    private AvlNode findMin(AvlNode t) {
        if (t == null) return null;
        while(t.left != null) {
            t = t.left;
        }
        return t;
    }

    /**
     * 一直往右走
     * @param t
     * @return
     */
    private AvlNode findMax(AvlNode t) {
        if (t == null) return null;
        while(t.right != null) {
            t = t.right;
        }
        return t;
    }

    /**
     * 与ADT插入操作完全相同，只是多了一个平衡操作
     * @param x
     * @param t
     * @return
     */
    private AvlNode insert(Integer x, AvlNode t) {
        if (t == null) {
            return new AvlNode(x,null,null);
        }

        if (x < t.element) {
            t.left = insert(x, t.left);
        }
        else if(x > t.element) {
            t.right = insert(x, t.right);
        }
        else {
            //do nothing
        }
        return balance(t);
    }

    /**
     * 与ADT的删除操作完全一样，只是多了哥平衡操作
     * @param x
     * @param t
     * @return
     */
    private AvlNode remove(Integer x, AvlNode t) {
        if (t == null) {
            return t;
        }

        if (x < t.element) {
            t.left = remove(x,t.left);
        }
        else if (x > t.element) {
            t.right = remove(x,t.right);
        }
        else {
            if (t.left == null && t.right == null) {
                t = null;
            }
            else if(t.left == null || t.right == null) {
                t = (t.left == null) ? t.right : t.left;
            }
            else {
                t.element = findMin(t.right).element;
                t.right = remove(t.element,t.right);
            }
        }
        return balance(t);
    }

    /**
     * 分为四种情况
     * LL 往左子树的左子树插入导致的不平衡 右旋
     * RR 往右子树的右子树插入导致的不平衡 左旋
     * LR 往左子树的右子树插入导致的不平衡 先对左子树左旋，再对根右旋
     * RL 往右子树的左子树插入导致的不平衡 先对右子树右旋，再对根左旋
     * @param t
     * @return
     */
    private AvlNode balance(AvlNode t) {
        if(t == null) return null;
        //L
        if (height(t.left) - height(t.right) > ALLOWED_IMBALANCE) {
            //LL
            //因为删除时可能会产生等于的情况，等号加不加无所谓，加等号只是为了相等的时候采用单旋转而不是双旋转提高效率
            if (height(t.left.left) - height(t.left.right) > 0) {
                t = rotateWithLeftChild(t);
            }
            //LR
            else {
                t = doubleWithLeftChild(t);
            }
        }
        //R
        else if (height(t.right) - height(t.left) > ALLOWED_IMBALANCE){
            //RR
            //因为删除时可能会产生等于的情况，等号加不加无所谓，加等号只是为了相等的时候采用单旋转而不是双旋转提高效率
            if(height(t.right.right) - height(t.right.left) > 0) {
                t = rotateWithRightChild(t);
            }
            //RL
            else {
                t = doubleWithRightChild(t);
            }
        }
        else {
            //do nothing
        }
        t.height = Math.max(height(t.left),height(t.right)) + 1;
        return t;
    }

    /**
     * LL 往左子树的左子树插入导致的不平衡 右旋：
     * 第一步：将根节点的左孩子替换此节点 AvlNode k = t.left;
     * 第二步：将 k节点的右孩子替换根节点的左孩子 t.left = k.right;
     * 第三步：将根节点替换为 k节点的右孩子 k.right = t;
     * @param t
     * @return
     */
    private AvlNode rotateWithLeftChild(AvlNode t) {
        AvlNode k = t.left;
        t.left = k.right;
        k.right = t;
        t.height = Math.max(height(t.left),height((t.right))) + 1;
        k.height = Math.max(height(k.left),t.height) + 1;
        return k;
    }

    /**
     * RR 往右子树的右子树插入导致的不平衡 左旋：
     * 第一步：将根节点的右孩子替换此节点 AvlNode k = t.right;
     * 第二步：将 k节点的左孩子替换根节点的右孩子 t.right = k.left;
     * 第三步：将根节点替换为 k节点的左孩子 k.left = t;
     * @param t
     * @return
     */
    private AvlNode rotateWithRightChild(AvlNode t) {
        AvlNode k = t.right;
        t.right = k.left;
        k.left = t;
        t.height = Math.max(height(t.left),height((t.right))) + 1;
        k.height = Math.max(height(k.left),t.height) + 1;
        return k;
    }

    /**
     * LR 往左子树的右子树插入导致的不平衡 先对左子树左旋，再对根右旋
     * @param t
     * @return
     */
    private AvlNode doubleWithLeftChild(AvlNode t) {
        t.left = rotateWithRightChild(t.left);
        return rotateWithLeftChild(t);
    }

    /**
     * RL 往右子树的左子树插入导致的不平衡 先对右子树右旋，再对根左旋
     * @param t
     * @return
     */
    private AvlNode doubleWithRightChild(AvlNode t) {
        t.right = rotateWithLeftChild(t.right);
        return rotateWithRightChild(t);
    }

    private void printTree(AvlNode t) {
        if (t == null) {
            return;
        }
        printTree(t.left);
        System.out.print(t.element + " ");
        printTree(t.right);
    }
}
